#include <vector>
#include <iostream>
#include <queue>
#include <climits>
using namespace std;

const long long INF = (1LL<<31)-1;

struct Edge 
{
    int to;
    long long weight;
    Edge(int t,long long w):to(t),weight(w){};
};

struct Node
{
    int id;
    long long dist;
    Node(int i ,long long d):id(i),dist(d){};
    bool operator>(const Node& other)
    {
        return this->dist>other.dist;
    }
};

vector<long long> dijistra(int n ,int s,vector<vector<Edge>>&graph)
{
    vector<bool>visited(n+1,false);
    vector<long long>dist(n+1,INF);
    priority_queue<Node,vector<Node>,greater<Node>>pq;
    
    // 将该初始化的初始化
    dist[s] = 0;
    pq.push(Node(s,0));

    // 广度优先遍历
    while (!pq.empty())
    {
        Node temp = pq.top();
        pq.pop();

        int u = temp.id;
        if (visited[u])
        {
            continue;
        }
        visited[u] = true;

        // 遍历为graph[u] (即为每一个节点出发的所有边)
        for (const Edge& e:graph[u])
        {
            int v = e.to;
            long long w = e.weight;

            // 如果s先到u的距离，加上u再到v的距离(也就是w)的总和，小于直接到v的距离
            // 那么就对s到v的距离进行更新，也就是一种动态规划
            if (!visited[v]&&dist[u]+w<dist[v])
            {
                dist[v] = dist[u]+w;
                pq.push(Node(v,dist[v]));
                // 这里不理解呀。这里是一套操作方法
                // 也就是对于每一个节点的下面所有节点，
                // 如果经过当前节点进入该节点的总路程小于之前获取的最优解
                // 那么就更新这个最优解，
                
                // 由于整个过程便遍历了，从每一节点出发的所有边，
                // 那么对于每一个节点，它的所有连接方法都可以被尝试一次，
                // 总会有一个是最优解
                // 输出时如果大于整数最大值，自然是不输出了
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0)  ;

    int n,m,s;
    cin>>n>>m>>s;

    vector<vector<Edge>>graph(n+1);
    
    for (int i = 0;i < m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        graph[u].push_back(Edge(v,w));
    }

    vector<long long>dist = dijistra(n,s,graph);
    
    return 0;
}